498,回溯算法解活字印刷
If you lose your purpose, it's like you're broken.
如果你生活漫无目的,那就好像你坏了。
问题描述
你有一套活字字模tiles,其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的非空字母序列的数目。
注意:本题中,每个活字字模只能使用一次。
示例 1:
输入:"AAB"
输出:8
解释:可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2:
输入:"AAABBC"
输出:188
提示:
1 <= tiles.length <= 7
tiles
由大写英文字母组成
回溯算法解决
这题实际上是让求输入的字符可以组成多少种不同的组合。之前也讲过很多种类似这样的题
但不同的是前面几道题字符出现的顺序是不会变的,比如第451题,他的子集有123,但不能有321。但这题不一样,输入AAB,他的序列中,A可以在B的前面也可以在B的后面。那么这道题使用回溯算法该怎么解,我们就以示例1为例来画个图看一下
前面介绍的几个组合的回溯算法,因为结果不能有重复的(比如[1,3]和[3,1]被认为是重复的结果),所以每次选择的时候都只能从前往后选。但这题中子集[A,B]和[B,A]被认为是两种不同的结果,所以每次都要从头开始选择,因为每个字符只能被使用一次,所以如果使用之后下次就不能再使用了,这里可以使用一个数组visit来标记有没有被使用。
但这里有个难点就是怎么过滤掉上面图中灰色的部分(也就是重复的部分)。举个例子,比如ABBCD,如果我们选择了第1个B,那么剩余的字符就变成了ABCD,这个时候我们再选择第2个B是可以的。但如果我们没选择第1个B,直接选择第2个B,那么剩余的字符就是ABCD,和上面重复了。所以代码大致是这样的
1if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
2 continue;
在前面讲450,什么叫回溯算法,一看就会,一写就废的时候,回溯算法的模板也被多次提及
1private void backtrack("原始参数") {
2 //终止条件(递归必须要有终止条件)
3 if ("终止条件") {
4 //一些逻辑操作(可有可无,视情况而定)
5 return;
6 }
7
8 for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
9 //一些逻辑操作(可有可无,视情况而定)
10
11 //做出选择
12
13 //递归
14 backtrack("新的参数");
15 //一些逻辑操作(可有可无,视情况而定)
16
17 //撤销选择
18 }
19}
最后来看下这题的最终代码
1public int numTilePossibilities(String tiles) {
2 char[] chars = tiles.toCharArray();
3 //先排序,目的是让相同的字符挨着,在下面计算的时候好过滤掉重复的
4 Arrays.sort(chars);
5 int[] res = new int[1];
6 backtrack(res, chars, new boolean[tiles.length()], tiles.length(), 0);
7 return res[0];
8}
9
10private void backtrack(int[] res, char[] chars, boolean[] used, int length, int index) {
11 //如果没有可以选择的就返回
12 if (index == length)
13 return;
14 //注意,这里的i每次都是从0开始的,不是从index开始
15 for (int i = 0; i < length; i++) {
16 //一个字符只能选择一次,如果当前字符已经选择了,就不能再选了。
17 if (used[i])
18 continue;
19 //过滤掉重复的结果
20 if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
21 continue;
22 //选择当前字符,并把它标记为已选择
23 used[i] = true;
24 res[0]++;//选择一个字符,就多了一种结果
25 //下一分支继续递归
26 backtrack(res, chars, used, length, index + 1);
27 //使用完之后再把它给复原。
28 used[i] = false;
29 }
30}
这里还可以换一种写法,先统计每个字符的数量,然后再使用,代码如下。原理都类似,但他不需要去重,因为这里根本不可能出现重复的。
1public int numTilePossibilities(String tiles) {
2 char[] chars = tiles.toCharArray();
3 //统计每个字符的数量
4 int[] count = new int[26];
5 for (char c : chars)
6 count[c - 'A']++;
7 int[] res = new int[1];
8 backtrack(res, count);
9 return res[0];
10}
11
12private void backtrack(int[] res, int[] arr) {
13 //遍历所有的字符
14 for (int i = 0; i < 26; i++) {
15 //如果当前字符使用完了再查找下一个
16 if (arr[i] == 0)
17 continue;
18 //如果没使用完就继续使用,然后把这个字符的数量减1
19 arr[i]--;
20 //使用一个字符,子集数量就会多一个
21 res[0]++;
22 backtrack(res, arr);
23 //当前字符使用完之后,把它的数量还原
24 arr[i]++;
25 }
26}
总结
前面也介绍过很多关于回溯算法的题,回溯算法有个大致的模板,只要掌握这个模板,然后对于不同的题在稍加修改,基本上都能做的出来。
●442,剑指 Offer-回溯算法解二叉树中和为某一值的路径
长按上图,识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧